Graphics Plus/Graphics Plus.iso/archivrs/general/lhasrc.exe/DHUF_.ASM

Assembly Source File | 1991-03-03 | 12KB | 689 lines

;***********************************************
;    dhuf_.asm -- Dynamic Huffman routine
;***********************************************
            page    0, 128

include    amscls.inc
$_init    GEN

CGROUP  GROUP   TEXT
DGROUP  GROUP   DATA,BSS

TEXT    segment byte public 'CODE'
        assume  cs:CGROUP, ds:DGROUP, ss:DGROUP
TEXT    ends

DATA    segment word public 'DATA'
DATA    ends

THRESHOLD    equ        3
N_CHAR        equ        (256 + 60 - THRESHOLD + 1)
TREESIZE_C  equ        (N_CHAR * 2)
TREESIZE_P  equ        (128 * 2)
TREESIZE    equ        (TREESIZE_C + TREESIZE_P)
ROOT_C      equ        0
ROOT_P      equ        TREESIZE_C

BSS     segment word public 'DATA'
        public  node_
node_            dw      N_CHAR + 128 dup (?)
        public  total_p_
total_p_        dw        1 dup (?)

BSS     ends

BSS            segment word public 'DATA'
start_        dw        1 dup(?)
end_        dw        1 dup(?)
BSS            ends

DATA    segment word public 'DATA'
DATA    ends

BSS     segment word public 'DATA'
        public  n_max_
n_max_            dw        1 dup (?)
        public  avail_
avail_          dw      1 dup (?)
        public  n1_
n1_             dw      1 dup (?)
        public  most_p_
most_p_         dw      1 dup (?)
        public  nn_
nn_             dw      1 dup (?)
        public  nextcount_
nextcount_      dw      2 dup (?)

BSS     ends

TEXT    segment byte public 'CODE'

;
;void start_c_dyn(void)
;

        public  start_c_dyn_
start_c_dyn_    proc    near
    push    cx
    push    dx
    push    si
    push    di
    mov        bx, 512
    mov        ax, maxmatch_
    add        ax, 256 - 2
    $_if <cmp n_max_, ax>, B
        mov        bx, n_max_
        dec        bx
    $_endif
    mov        n1_, bx
    push    ds
    pop        es
    cld
    xor        ax, ax
    mov        cx, TREESIZE_C
    mov        di, offset DGROUP:block_
    rep        stosw
    mov        cx, TREESIZE_C
    mov        di, offset DGROUP:stock_
    $_do
        stosw
        inc        ax
        inc        ax
    $_until <LOOP>
    mov        di, offset DGROUP:node_
    mov        bx, n_max_
    mov        cx, bx
    dec        bx
    shl        bx, 1
    mov        edge_[2], bx
    shl        bx, 1
    push    bx
    mov        ax, 1
    mov        dx, 0ffffh
    $_do
        mov        freq_[bx], ax
        mov        block_[bx], 2
        mov        child_[bx], dx
        mov        [di], bx
        dec        dx
        dec        dx
        dec        bx
        dec        bx
        inc        di
        inc        di
    $_until <LOOP>
    mov     word ptr DGROUP:[avail_], 4
    pop        di
    $_do
        mov        ax, freq_[di]
        add        ax, freq_[di - 2]
        mov        freq_[bx], ax
        mov        child_[bx], di
        mov        parent_[di], bx
        mov        parent_[di - 2], bx
        $_if <cmp ax, freq_[bx + 2]>, E
            mov        si, block_[bx + 2]
        $_else
            mov        si, avail_
            add        avail_, 2
            mov        si, stock_[si]
        $_endif
        mov        block_[bx], si
        mov        edge_[si], bx
        sub        di, 4
        dec        bx
        dec        bx
    $_until , S
    pop        di
    pop        si
    pop        dx
    pop        cx
    ret
start_c_dyn_    endp


;
;static void start_p_dyn(void)
;

start_p_dyn_    proc    near
    push    cx
    mov     freq_[ROOT_P * 2], 1
    mov     child_[ROOT_P * 2], not (N_CHAR * 2)
    mov     node_[N_CHAR * 2], ROOT_P * 2
    mov        bx, avail_
    add        avail_, 2
    mov        bx, stock_[bx]
    mov        block_[ROOT_P * 2], bx
    mov        edge_[bx], ROOT_P * 2
    mov        most_p_, ROOT_P * 2
    mov        ax, 1
    mov        cx, dicbit_
    shl        ax, cl
    mov        nn_, ax
    xor        ax, ax
    mov        nextcount_, 64
    mov        nextcount_[2], ax
    mov        total_p_, 0
    pop        cx
    ret
start_p_dyn_    endp


;
;void decode_start_dyn(void)
;

            public  decode_start_dyn_
decode_start_dyn_    proc    near
    mov        n_max_, 286
    mov        maxmatch_, 256
    call    init_getbits_
    call    start_c_dyn_
    call    start_p_dyn_
    ret
decode_start_dyn_    endp


;
;static void reconst(int start, int end)
;

            public    reconst_
reconst_    proc    near
    push    cx
    push    dx
    push    si
    push    di
    mov        start_, ax
    mov        end_, bx
    mov        si, ax
    mov        di, ax
    $_while <cmp si, end_>, L
        mov        bx, child_[si]
        $_if <or bx, bx>, L
            mov        ax, freq_[si]
            inc        ax
            shr        ax, 1
            mov        freq_[di], ax
            mov        child_[di], bx
            inc        di
            inc        di
        $_endif
        mov        bx, block_[si]
        $_if <cmp edge_[bx], si>, E
            sub        avail_, 2
            mov        ax, bx
            mov        bx, avail_
            mov        stock_[bx], ax
        $_endif
        inc        si
        inc        si
    $_enddo
    dec        di
    dec        di
    dec        si
    dec        si
    mov        bx, si
    dec        bx
    dec        bx
    $_while <cmp si, start_>, GE
        $_while <cmp si, bx>, GE
            mov        ax, freq_[di]
            mov        freq_[si], ax
            mov        ax, child_[di]
            mov        child_[si], ax
            dec        di
            dec        di
            dec        si
            dec        si
        $_enddo
        mov        ax, freq_[bx]
        add        ax, freq_[bx + 2]
        push    bx
        mov        bx, start_
        $_while <cmp ax, freq_[bx]>, B
            inc        bx
            inc        bx
        $_enddo
        $_while <cmp di, bx>, GE
            mov        dx, freq_[di]
            mov        freq_[si], dx
            mov        dx, child_[di]
            mov        child_[si], dx
            dec        si
            dec        si
            dec        di
            dec        di
        $_enddo
        mov        freq_[si], ax
        pop        bx
        inc        bx
        inc        bx
        mov        child_[si], bx
        dec        si
        dec        si
        sub        bx, 6
    $_enddo
    xor        ax, ax
    mov        si, start_
    $_while <cmp si, end_>, L
        mov        di, child_[si]
        $_if <or di, di>, S
            not        di
            mov        node_[di], si
            not        di
        $_else
            mov        parent_[di], si
            mov        parent_[di - 2], si
        $_endif
        mov        dx, freq_[si]
        $_if <cmp dx, ax>, E
            mov        block_[si], bx
        $_else
            mov        bx, avail_
            add        avail_, 2
            mov        bx, stock_[bx]
            mov        block_[si], bx
            mov        edge_[bx], si
            mov        ax, dx
        $_endif
        inc        si
        inc        si
    $_enddo
    pop        di
    pop        si
    pop        dx
    pop        cx
    ret
reconst_    endp

;
;    static int swap_inc(int p)
;

            public    swap_inc_
swap_inc_    proc    near
;    push    dx
;    push    si
;    push    di
    mov        si, ax
    mov        bx, block_[si]
    mov        di, edge_[bx]
    $_if <cmp di, si>, NE
        push    bx
        mov        bx, child_[si]
        mov        dx, child_[di]
        mov        child_[si], dx
        mov        child_[di], bx
        $_if <or bx, bx>, NS
            mov        parent_[bx], di
            mov        parent_[bx - 2], di
        $_else
            not        bx
            mov        node_[bx], di
        $_endif
        mov        bx, dx
        $_if <or bx, bx>, NS
            mov        parent_[bx], si
            mov        parent_[bx - 2], si
        $_else
            not        bx
            mov        node_[bx], si
        $_endif
        mov        si, di
        pop        bx
        jmp        Adjust
    $_endif
    $_if <cmp bx, block_[si + 2]>, E
Adjust:
        add        edge_[bx], 2
        inc        freq_[si]
        mov        ax, freq_[si]
        $_if <cmp ax, freq_[si - 2]>, E
            mov        ax, block_[si - 2]
            mov        block_[si], ax
        $_else
            mov        bx, avail_
            add        avail_, 2
            mov        bx, stock_[bx]
            mov        block_[si], bx
            mov        edge_[bx], si
        $_endif
    $_else
        inc        freq_[si]
        mov        ax, freq_[si]
        $_if <cmp ax, freq_[si - 2]>, E
            sub        avail_, 2
            mov        di, avail_
            mov        stock_[di], bx
            mov        ax, block_[si - 2]
            mov        block_[si], ax
        $_endif
    $_endif
    mov        ax, parent_[si]
;    pop        di
;    pop        si
;    pop        dx
    ret
swap_inc_    endp


;
;    static void update_c(int p)
;

            public    update_c_
update_c_    proc    near
    $_if <cmp freq_[ROOT_C * 2], 8000h>, E
        push    ax
        mov        bx, n_max_
        shl        bx, 1
        dec        bx
        shl        bx, 1
        xor        ax, ax
        call    reconst_
        pop        ax
    $_endif
    inc        freq_[ROOT_C * 2]
    mov        bx, ax
    mov        ax, node_[bx]
    $_do
        call    swap_inc_
    $_until <cmp ax, ROOT_C * 2>, E
    ret
update_c_    endp


;
;    static void update_p(int p)
;

            public    update_p_
update_p_    proc    near
    $_if <cmp total_p_, 8000h>, E
        push    ax
        mov        bx, most_p_
        inc        bx
        inc        bx
        mov        ax, ROOT_P * 2
        call    reconst_
        mov        ax, 0ffffh
        xchg    ax, freq_[ROOT_P * 2]
        mov        total_p_, ax
        pop        ax
    $_endif
    mov        bx, ax
    mov        ax, node_[bx + N_CHAR * 2]
    $_while <cmp ax, ROOT_P * 2>, NE
        call    swap_inc_
    $_enddo
    inc        total_p_
    ret
update_p_    endp


;
;    static void make_new_node(int p)
;

make_new_node_    proc    near
    push    si
    push    di
    mov        di, most_p_
    mov        bx, child_[di]
    mov        child_[di + 2], bx
    not        bx
    lea        si, [di + 2]
    mov        node_[bx], si
    mov        si, ax
    add        si, N_CHAR * 2
    not        si
    mov        child_[di + 4], si
    lea        si, [di + 4]
    mov        child_[di], si
    mov        bx, freq_[di]
    mov        freq_[di + 2], bx
    mov        freq_[di + 4], 0
    mov        bx, block_[di]
    mov        block_[di + 2], bx
    $_if <cmp di, ROOT_P * 2>, E
        mov        freq_[ROOT_P * 2], 0ffffh
        mov        bx, block_[ROOT_P * 2]
        add        edge_[bx], 2
    $_endif
    mov        parent_[di + 2], di
    mov        parent_[di + 4], di
    add        di, 4
    mov        most_p_, di
    mov        bx, ax
    mov        node_[bx + N_CHAR * 2], di
    mov        bx, avail_
    add        avail_, 2
    mov        bx, stock_[bx]
    mov        block_[di], bx
    mov        edge_[bx], di
    call    update_p_
    pop        di
    pop        si
    ret
make_new_node_    endp


;
;    static void encode_c_dyn(int c)
;

encode_c_dyn_    proc    near
    push    cx
    push    dx
    push    si
;    push    di
;    mov        di, -1
;    $_if <cmp ax, n1_>, AE
;        mov        di, ax
;        mov        ax, n1_
;        sub        di, ax
;    $_endif
    shl        ax, 1
    mov        bx, ax
    mov        bx, node_[bx]
    xor        dx, dx
    mov        cx, dx
    $_do
        mov        si, bx
        shr        bx, 1
        shr        bx, 1
        rcr        dx, 1
        rcr        ch, 1
        inc        cx
        mov        bx, parent_[si]
    $_until <cmp bx, ROOT_C * 2>, E
    mov        si, ax
    $_if <cmp cl, 16>, A
        mov        bx, dx
        mov        al, 16
        sub        cl, al
        call    putcode_
        mov        dx, cx
        xor        dl, dl
    $_endif
    mov        ax, cx
    mov        bx, dx
    call    putcode_
;    $_if <or di, di>, NS
;        mov        bx, di
;        mov        ax, 8
;        call    putbits_
;    $_endif
    mov        ax, si
    call    update_c_
;    pop        di
    pop        si
    pop        dx
    pop        cx
    ret
encode_c_dyn_    endp

;
;    ushort decode_c_dyn(void)
;

        public  decode_c_dyn_
decode_c_dyn_    proc    near
    push    cx
    push    dx
    push    si
    push    di
    mov        si, child_[ROOT_C * 2]
    mov        cx, 16
    mov        bx, bitbuf_
    $_do
        $_if <dec cx>, S
            mov        ax, 16
            mov        cx, 15
            call    fillbuf_
            mov        bx, bitbuf_
        $_endif
        shl        bx, 1
        sbb        ax, ax
        shl        ax, 1
        add        si, ax
        mov        si, child_[si]
    $_until <or si, si>, LE
    mov        al, 16
    sub        al, cl
    call    fillbuf_
    not        si
    mov        ax, si
    push    si
    call    update_c_
    pop        si
    shr        si, 1
    $_if <cmp si, n1_>, E
        mov        ax, 8
        call    getbits_
        add        si, ax
    $_endif
    mov        ax, si
    pop        di
    pop        si
    pop        dx
    pop        cx
    ret
decode_c_dyn_    endp


;
;    ushort decode_p_dyn(void)
;

        public  decode_p_dyn_
decode_p_dyn_    proc    near
    push    cx
    push    dx
    push    si
    push    di
    $_while <cmp nextcount_ + 2, 0>, E, AND
    mov        ax, nextcount_
    $_c <cmp count_, ax>, G
        mov        cl, 6 - 1
        shr        ax, cl
        call    make_new_node_
        add        nextcount_, 64
        mov        ax, nextcount_
        $_if <cmp ax, nn_>, AE
            mov        ax, 0ffffh
            mov        nextcount_, ax
            mov        nextcount_ + 2, ax
        $_endif
    $_enddo
    mov        si, child_[ROOT_P * 2]
    mov        cx, 16
    mov        bx, bitbuf_
    $_while <or si, si>, G
        $_if <dec cx>, S
            mov        ax, 16
            mov        cx, 15
            call    fillbuf_
            mov        bx, bitbuf_
        $_endif
        shl        bx, 1
        sbb        ax, ax
        shl        ax, 1
        add        si, ax
        mov        si, child_[si]
    $_enddo
    mov        al, 16
    sub        al, cl
    call    fillbuf_
    not        si
    sub        si, N_CHAR * 2
    mov        ax, si
    push    si
    call    update_p_
    mov        ax, 6
    call    getbits_
    pop        si
    mov        cl, 6 - 1
    shl        si, cl
    add        ax, si
    pop        di
    pop        si
    pop        dx
    pop        cx
    ret
decode_p_dyn_    endp


;
;    void output_dyn(int code, unsigned int pos)
;

                public    output_dyn_
output_dyn_    proc    near
    $_if <cmp ax, 100h>, AE
        push    bx
        call    encode_c_dyn_
        pop        ax
        jmp        encode_p_st0_
    $_endif
    jmp        encode_c_dyn_
output_dyn_    endp


;
;    void encode_end_dyn(void)
;

        public  encode_end_dyn_
encode_end_dyn_    proc    near
    mov        al, 7
    xor        bx, bx
    jmp        putcode_
encode_end_dyn_    endp


        EXTRN   getbits_:near
        EXTRN   fillbuf_:near
        EXTRN   putcode_:near
        EXTRN   putbits_:near
        EXTRN   init_getbits_:near
        EXTRN   encode_p_st0_:near

TEXT    ends

        EXTRN   dicbit_:word
        EXTRN   count_:word
        EXTRN   block_:word
        EXTRN   parent_:word
        EXTRN   child_:word
        EXTRN   maxmatch_:word
        EXTRN   freq_:word
        EXTRN   stock_:word
        EXTRN   edge_:word
        EXTRN   maxmatch_:word
        EXTRN   bitbuf_:word

        END